NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/1442

Internet Message Format | 1996-08-06 | 3.7 KB

Path: rap.SanDiegoCA.ATTGIS.COM!es013!jbc
From: [e-mail] (Jim Chapman)
Newsgroups: comp.lang.c++
Subject: Re: deque container - how to implement?
Date: 11 Jan 1996 01:17:21 GMT
Organization: AT&T Global Information Solutions
Distribution: world
Message-ID: <4d1of1$[e-mail]>
References: <4cvepv$[e-mail]>
Reply-To: [e-mail]
NNTP-Posting-Host: es013.elsegundoca.attgis.com

In article [e-mail], [e-mail]  ( Todd Knarr ) writes:
> In <4ct0c3$[e-mail]>, David Byrden <[e-mail]> writes:
> >I have hardly studied deque and have never seen an implementation, but I
> >will bet that it works like this; it consists of a contigous block of
> >elements in the MIDDLE of a larger block of free space. Adding elements
> >is fast because there is free space at each end. When it expands to bump
> >either end of its free space, it allocates a larger block of memory from
> >the heap and copies all its contents into the MIDDLE of the new block.
> >Altering things in the middle is slow because the elements must remian
> >contiguous, so up to half of the data will need to move.
>
> They can be implemented that way ( based on an array of elements ), but
> it's unusual because of the physical shuffling needed. More often they
> are implemented using pointers. For a deque of objects of class T, you
> make a node type like so ( for a fully non-intrusive list ):
>
> struct Node
> {
>     Node *pNext, *pPrev;
>     T *pElement;
> };
>
> You start out with head and tail pointers set to the first and last
> nodes in the list. Inserting an item simply involves making a new node
> for it, pointing that node's pNext and pPrev pointers to the nodes
> just before and after it in the list, then pointing those node's pNext
> and pPrev pointers to the new node as appropriate. As sample code,
> assuming pInsertPoint points to the node I want to insert after and
> pNewNode points to the node to insert with pElement filled in, I would
> do:
>
> pNewNode->pPrev = pInsertPoint;
> pNewNode->pNext = pInsertPoint->pNext;
> pInsertPoint->pNext->pPrev = pNewNode;
> pInsertPoint->pNext = pNewNode;
>
> Removing an element simply involves finding the node and cutting it out
> of the chain by pointing the pNext and pPrev pointers of the nodes before
> and after it to each other.
>
> Implementation notes:
>
> 1) The idea of a Node structure seperate from the element is solely to
> allow building lists of things without needing any fields in the things
> to be put on the list. You can also put the next and previous pointers
> in the actual items and avoid allocating and deallocating nodes all the
> time.
>
> 2) Most implementations that use Node structures use two dummy nodes to
> anchor the head and tail of the list. They usually have NULL pElement
> pointers to distinguish them from real nodes. This eliminates special-case
> code to deal with an empty list or the ends of the list.
>
> --
> Todd Knarr : [e-mail]      |  finger for PGP public key
>                                       |  Member, USENET Cabal
>
> Seriously, I don't want to die just yet.  I don't care how
> good-looking they are, I! don't! want! to! die!"
>                                         -- Megazone ( UF1 )
>

In STL, deque<T> is supposed to support random access in constant time, so
a linked list implemention wouldn't do.  The first poster was closer to
the mark.

---
 ====  AT&T        | Jim Chapman             |
=--=== Global      | Multimedia Projects     | [e-mail]
=--=== Information | 100 N. Sepulveda Blvd.  |   Voice: [phone]
 ====  Solutions   | El Segundo, CA 90245    |   FAX:   [phone]